package algotithm.leetcode.listnode.test708;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/22-22:35
 * @URL https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/
 * @Title 708. 循环有序列表的插入
 */
class Node {
    int val;
    Node next;

    public Node (int val) {
        this.val = val;
    }
    public Node (int val,Node next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node newNode = new Node(insertVal, null);
            newNode.next = newNode;
            return newNode;
        }

        Node prev = head;
        Node curr = head.next;
        boolean toInsert = false;

        do {
            if (prev.val <= insertVal && insertVal <= curr.val) {
                // Case 1).
                toInsert = true;
            } else if (prev.val > curr.val) {
                // Case 2).
                if (insertVal >= prev.val || insertVal <= curr.val) {
                    toInsert = true;
                }
            }

            if (toInsert) {
                prev.next = new Node(insertVal, curr);
                return head;
            }

            prev = curr;
            curr = curr.next;
        } while (prev != head);

        // Case 3).
        prev.next = new Node(insertVal, curr);
        return head;
    }
}


